/*
@author: ZZH
@date: 2021-11-05
@time: 14:21:15
@info: 红黑树基本操作和数据结构，包括创建，遍历，插入，查找和删除,但并不是最终使用的接口，最终的接口请使用红黑树实现文件内的
*/
#pragma once
#include "stdint.h"
#include "stdlib.h"

#ifdef __cplusplus
extern "C" {
#endif

/*数据类型定义*/
typedef enum
{
    RBT_Red = 0,
    RBT_Black
} RBTColor_t; //红黑树颜色定义

typedef enum
{
    RBT_Big,
    RBT_Small,
    RBT_Equal
} RBT_CompareResult_t; //红黑树key比较结果

typedef struct __RB_TreeNode
{
    RBTColor_t color;
    struct __RB_TreeNode* left, * right, * parent;
} RBTreeNode_t, * pRBTreeNode_t; //红黑树节点定义

typedef struct RBTree_t RBTree_t, *pRBTree_t;

//红黑树用到的内存操作函数类型定义
typedef void (*__RBT_Free)(void*);
typedef RBT_CompareResult_t(*__RBT_Compare)(pRBTreeNode_t node, void* key);//
typedef void (*__RBT_Visit)(pRBTree_t tree, pRBTreeNode_t node, uint32_t level);
typedef void (*__RBT_Copy)(pRBTreeNode_t node1, pRBTreeNode_t node2);

typedef struct RBTree_t
{
    pRBTreeNode_t root;
    __RBT_Free free;
    __RBT_Compare compare;
    __RBT_Visit visit;
    __RBT_Copy copy;//拷贝方向 参数1 <- 参数2
} RBTree_t, * pRBTree_t; //红黑树结构
/*数据类型定义结束*/


/*********************************************************************************
对外开放的接口
*********************************************************************************/
/*遍历操作,所有的子树遍历均默认左子树优先*/
//先序遍历，对外开放的接口
#define RBT_FirstOrderRec(tree) _RBT_FirstOrderRecursive(tree, tree->root, 0)
//中序遍历，对外开放的接口
#define RBT_MiddleOrderRec(tree) _RBT_MiddleOrderRecursive(tree, tree->root, 0)
//后序遍历，对外开放的接口
#define RBT_LastOrderRec(tree) _RBT_LastOrderRecursive(tree, tree->root, 0)

//先序遍历，对外开放的接口
#define RBT_FirstOrderFsm(tree) _RBT_FirstOrderFsm(tree, tree->root, 0)
//中序遍历，对外开放的接口
#define RBT_MiddleOrderFsm(tree) _RBT_MiddleOrderFsm(tree, tree->root, 0)
//后序遍历，对外开放的接口
#define RBT_LastOrderFsm(tree) _RBT_LastOrderFsm(tree, tree->root, 0)
/*遍历操作结束*/

/*基本操作,节点插入，查找等操作与具体的键值对类型有关，因此此处无法提供此类接口*/
//计算红黑树内节点数量
uint32_t RBT_CountObjects(pRBTree_t tree);
//计算红黑树高度
uint32_t RBT_Height(pRBTree_t tree);
//清空红黑树全部子树，状态机实现
void RBT_Clear(pRBTree_t tree);
/*基本操作结束*/


/*********************************************************************************
不开放的接口
*********************************************************************************/

/*遍历操作,所有的子树遍历均默认左子树优先*/
//先序遍历红黑树,外部可调用但不推荐，递归形式
void _RBT_FirstOrderRecursive(pRBTree_t tree, pRBTreeNode_t root, uint32_t level);
//中序遍历红黑树,外部可调用但不推荐，递归形式
void _RBT_MiddleOrderRecursive(pRBTree_t tree, pRBTreeNode_t root, uint32_t level);
//后序遍历红黑树,外部可调用但不推荐，递归形式
void _RBT_LastOrderRecursive(pRBTree_t tree, pRBTreeNode_t root, uint32_t level);

//先序遍历红黑树,外部可调用但不推荐，状态机实现O(1)空间复杂度
void _RBT_FirstOrderFsm(pRBTree_t tree, pRBTreeNode_t root, uint32_t level);
//中序遍历红黑树,外部可调用但不推荐，状态机实现O(1)空间复杂度
void _RBT_MiddleOrderFsm(pRBTree_t tree, pRBTreeNode_t root, uint32_t level);
//后序遍历红黑树,外部可调用但不推荐，状态机实现O(1)空间复杂度
void _RBT_LastOrderFsm(pRBTree_t tree, pRBTreeNode_t root, uint32_t level);
/*遍历操作结束*/

/*基本操作*/
//静态创建红黑树，也就是红黑树结构本身为静态结构体，节点依然是动态创建出来的，其他同上
void __RBT_CreateStatic(pRBTree_t tree);
//插入节点，此接口应当在具体的实现文件内调用
uint8_t __RBT_InsertNode(pRBTree_t tree, pRBTreeNode_t node, void* key);
//删除节点，此接口应当在具体的实现文件内调用
uint8_t __RBT_DeleteNode(pRBTree_t tree, pRBTreeNode_t node);
//根据键带条件搜索节点，此接口应当在具体的实现文件内调用
pRBTreeNode_t __RBT_SearchNodeCond(pRBTree_t tree, void* key, RBT_CompareResult_t cond);
/*
@brief 返回某节点后继节点
@param node 任意节点
@return node的后继节点
*/
pRBTreeNode_t __RBT_Next(pRBTreeNode_t node);
/*基本操作结束*/

//https://www.jianshu.com/p/e136ec79235c

#ifdef __cplusplus
}
#endif
